Error correcting coding of data enables reliability to be provided for the transmission of the data over a network and to correct possible losses related to the transmission over a channel by generating redundancy information.
In the following portion of the document, mesh networks are understood to mean telecommunications networks organized such that certain nodes repeat a data message received either for its broadcast, or when the distance from the original sender to the recipient exceeds the physical range of the signal and necessitates relaying of the data message by one of the nodes.
A mesh network example is represented in FIG. 1 in which the source (node “0”) sends a message bound for the receiver (node “z”). Several relays (nodes “r”, last, “t”, “u”) receive one or several copies of the message from previous nodes, then decode them in part in order to determine the recipient of the message. If the recipient is other than the relay, the latter re-codes each copy received and re-sends them over the network towards the recipient node “z” since the latter is beyond the direct range of the source node.
The prior art proposes several encoding/decoding solutions not specifically dedicated to mesh networks.
In particular the document U.S. Pat. No. 7,089,477 is known which relies on message repetition principles to create a class of error correcting codes referred to as repeat accumulate codes.
In the encoding/decoding system of the prior art, a repetition code is explicitly created at the original sender by the duplication of data of a message to transmit and the concatenation of the data so repeated.
This repetition consists of a repetition code or “external code” which, according to code theory, constitutes information that is additional to the actual redundancy information (“internal code”) generated by the coding of a single copy of the message, for example by a convolutional code.
According to the document U.S. Pat. No. 7,089,477, the repeated data are then interleaved taking into account all the copies of the message.
In these conditions, the decoding of the message at a recipient requires the reception of the entirety of the copies created and transmitted as well as the preservation of the order of their interleaving along the communication channel or channels.
However, in mesh networks, the relay nodes create additional copies of a received message. For example, when a relay node is connected to more than two nodes, on reception of a message coming from one of the nodes, it may re-transmit the received message to the other nodes (at least two other nodes), by duplicating the received message. The copies created constitute an implicit repetition code.
In the case of FIG. 1, the relay node “s” duplicates a message received from the sender (node “0”) to the node “t” and the node “u”. The node “t” transmits the messages received from the nodes “0” and “s” to the node “z”. The node “u” also transmits the message received from the node “s” to the recipient node “z”. The receiver (node “z”) thus receives several copies of the same original message, it being possible for each of those copies to be protected by a redundancy code, for example, for wireless transmission channels, a convolutional code (CC).
This implies that the transmitted messages may take several paths and arrive at the receiver at variable times. The order of reception of the messages at the receiver in this case does not necessarily correspond to the order of sending onto the network. The result of this is that it is impossible for the decoder of the prior art to recover the initial message.
It is also noted that some copies of coded data may be lost, sometimes due to malfunctions of the physical layer of the network that cannot be predicted (for example the interruption of a physical link). In this case, not all the initial copies can be received by the decoder. Once again, the decoder of the prior art is then incapable of recovering the initial message.
The decoder of the prior art is consequently not adapted to the topology of mesh networks.